package interview.preparation;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;

public class Graph {

	public static Map<String, Vertex> vertexes = new HashMap<String, Vertex>();

	public class Vertex implements Comparable<Vertex> {
		public Vertex(){}
		public Vertex (String label){
			this.label=label;
		}
		String label;
		
		List<Vertex> in = new ArrayList<Vertex>();
		List<Vertex> out = new ArrayList<Vertex>();
		
		boolean visited = false;

		@Override
		public int compareTo(Vertex a) {
			return label.compareTo(a.label);
		}
		
		@Override
		public boolean equals(Object other){
			return this.label.equals( ((Vertex)(other)).label);
		}
		
		@Override
		public int hashCode(){
			return label.hashCode();
		}
	}

	class Edge {
		int weight;
		Vertex source;
		Vertex destination;
		String label;
	}

	public void addVertex(String label) {
		Vertex vertex = new Vertex();
		vertex.label = label;
		vertexes.put(label, vertex);
	}

	public void addEdge(String source, String destination, int weight, String label) {
		Edge edge = new Edge();
		edge.weight = weight;
		
		//Directed
		(vertexes.get(source)).out.add(vertexes.get(destination));
		(vertexes.get(destination)).in.add(vertexes.get(source));
		//Undirected
		//(vertexes.get(destination)).undirected.add(vertexes.get(source));
		
		edge.source = vertexes.get(source);
		edge.destination = vertexes.get(destination);
		edge.label = label;
	}

	void traverseGraph(Vertex root) {
		Queue<Vertex> queue = new LinkedList<Vertex>();
		queue.offer(root);
		Vertex data;
		while (queue.peek() != null) {
			data = queue.poll();
			if (!data.visited) {
				System.out.println(" " + data.label);
				data.visited = true;
				Collections.sort(data.out);
				for (Vertex ver : data.out) {
					queue.offer(ver);

				}
			}
		}

	}

	
	void traverseGraphDFS(Vertex root) {
		Queue<Vertex> queue = new LinkedList<Vertex>();
		queue.offer(root);
		Vertex data;
		while (queue.peek() != null) {
			data = queue.poll();
			if (!root.visited) {
				System.out.println(" " + root.label);
				root.visited = true;
				Collections.sort(root.out);
				for (Vertex ver : root.out) {
					traverseGraphDFS(ver);
				}
			}
		}
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {

		Graph myGraph = new Graph();
//		myGraph.addVertex("A");
//		myGraph.addVertex("B");
//		myGraph.addVertex("C");
//		myGraph.addVertex("D");
//		myGraph.addVertex("E");
//		myGraph.addVertex("F");
//		myGraph.addVertex("J");
//		myGraph.addVertex("K");
//		myGraph.addVertex("G");

		myGraph.addEdge("A", "B", 10, "AB");
		myGraph.addEdge("A", "C", 10, "AC");
		myGraph.addEdge("A", "F", 10, "AF");
		myGraph.addEdge("B", "C", 10, "BC");
		myGraph.addEdge("B", "G", 10, "BG");
		myGraph.addEdge("C", "F", 10, "CF");
		myGraph.addEdge("D", "C", 10, "DC");
		myGraph.addEdge("E", "C", 10, "EC");
		myGraph.addEdge("E", "J", 10, "EJ");
		myGraph.addEdge("F", "D", 10, "FD");
		myGraph.addEdge("J", "D", 10, "JD");
		myGraph.addEdge("J", "K", 10, "JK");
		myGraph.addEdge("K", "E", 10, "KE");
		myGraph.addEdge("K", "G", 10, "KG");
		myGraph.addEdge("G", "E", 10, "GE");
		myGraph.addEdge("G", "C", 10, "GC");

		
		myGraph.traverseGraphDFS(vertexes.get("A"));
	}

}
